// BinaryTree 二叉树

// 度:节点含有的子树的个数称为节点的度
// 树的度:最大的节点的度称为树的度
// 考虑到没有很好的定义，因此二叉树一般不考虑增删查改
// 每一层递归函数都有一个i，下一层放了值，i++不会影响上一层函数中的i

// 二叉树的一些常见性质
// 1.若规定根节点的层数为1，则每层最多有2^(i-1)个节点
// 2.若规定根节点的层数为1，则深度为h的二叉树的最大节点数为2*h-1
// 3.对任何一棵二叉树，如果度为0其叶节点的个数为n0，度为2其叶节点的个数为n2，则有n0=n2+1
// 4.若规定根节点的层数为1，具有n个节点的满二叉树的深度h=logN;

// 二叉树用作数据存储意义不大，不如线性表
// 搜索二叉树搜索查找效率高，有意义
// 数组存储适用于完全二叉树和满二叉树，否则会造成空间浪费
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
#include <string.h>

typedef int BTDataType;
typedef struct BinaryTreeNode
{
    struct BinaryTreeNode* pLeft;
    struct BinaryTreeNode* pRight;
    // struct BinaryTreeNode* pParent;
    BTDataType data;
}BTNode;

typedef BTNode* QDataType;
typedef struct QueueNode
{
    struct QueueNode* next;
    QDataType data;
}QNode;

// 引入队列，为了层序遍历和isCompleteTree函数
typedef struct Queue
{
    QNode* head;
    QNode* tail;
    int size;
}Queue;

// 初始化
void QueueInit(Queue* pq);
void QueueDestroy(Queue* pq);

// 队尾入,队头出
void QueuePush(Queue* pq, QDataType val);
void QueuePop(Queue* pq);

// 获取数据，判断是否为空
QDataType QueueFront(Queue* pq);
QDataType QueueBack(Queue* pq);
int QueueSize(Queue* pq);
bool isQueueEmpty(Queue* pq);

void QueueInit(Queue* pq)
{
    assert(pq);

    pq->head = pq->tail = NULL;
    pq->size = 0;
}

void QueueDestroy(Queue* pq)
{
    assert(pq);

    QNode* cur = pq->head;
    while (cur != NULL){
        QNode* next = cur->next;
        free(cur);
        cur = next;
    }
    pq->head = pq->tail = NULL;
    pq->size = 0;
}

void QueuePush(Queue* pq, QDataType val)
{
    assert(pq);

    QNode* newNode = (QNode*)malloc(sizeof(QNode));
    if (newNode == NULL){
        printf("malloc fail\n");
        exit(-1);
    }

    newNode->data = val;
    newNode->next = NULL;

    if (pq->tail == NULL){
        pq->head = pq->tail = newNode;
    }
    else {
        pq->tail->next = newNode;
        pq->tail = newNode;
    }
    pq->size++;
}

void QueuePop(Queue* pq)
{
    assert(pq);
    assert(pq->head);

    if (pq->head->next == NULL)
    {
        free(pq->head);
        pq->head = pq->tail = NULL;
    }
    else {
        QNode* next = pq->head->next;
        free(pq->head);
        pq->head = next;
    }
    pq->size--;
}

QDataType QueueFront(Queue* pq)
{
    assert(pq);
    assert(pq->head);

    return pq->head->data;
}

QDataType QueueBack(Queue* pq)
{
    assert(pq);
    assert(pq->head);

    return pq->tail->data;
}

int QueueSize(Queue* pq)
{
    assert(pq);

    return pq->size;
}

bool isQueueEmpty(Queue* pq)
{
    assert(pq);

    return pq->size == 0;
}

int max(int num1, int num2)
{
    return num1 > num2 ? num1 : num2;
}

BTNode* BuyBTNode(BTDataType val)
{
    BTNode* newNode = (BTNode*)malloc(sizeof(BTNode));
    if (newNode == NULL){
        perror("malloc fail\n");
        exit(-1);
    }

    newNode->pLeft = NULL;
    newNode->pRight = NULL;
    newNode->data = val;

    return newNode;
}

BTNode* CreateTree(void)
{
    BTNode* n1 = BuyBTNode(1);
    BTNode* n2 = BuyBTNode(2);
    BTNode* n3 = BuyBTNode(3);
    BTNode* n4 = BuyBTNode(4);

    n1->pLeft = n2;
    n1->pRight = n3;
    n2->pLeft = n4;

    return n1;
}

// 前序
void PrevOrder(BTNode* root)
{
    if (root == NULL){
        printf("NULL ");
        return ;
    }
    
    printf("%d ", root->data);
    PrevOrder(root->pLeft);
    PrevOrder(root->pRight);
}

// 中序
void InOrder(BTNode* root)
{
    if (root == NULL){
        printf("NULL ");
        return ;
    }

    InOrder(root->pLeft);
    printf("%d ", root->data);
    InOrder(root->pRight);
}

// 后序
void PostOrder(BTNode* root)
{
    if (root == NULL){
        printf("NULL ");
        return ;
    }

    PostOrder(root->pRight);
    PostOrder(root->pLeft);
    printf("%d ", root->data);
}
/*
 * 线程不安全，一般不使用
int size = 0;
void TreeSize(BTNode* root)
{
    if (root == NULL){
        return ;
    }

    size++;
    TreeSize(root->pLeft);
    TreeSize(root->pRight);

}
*/

int TreeSize(BTNode* root)
{
    return root == NULL ? 0 : TreeSize(root->pLeft) + 1 + TreeSize(root->pRight);
}

// 求叶子节点的个数
int TreeLeafSize(BTNode* root)
{
    if (root == NULL){
        return 0;
    }

    if (root->pLeft == NULL && root->pRight == NULL){
        return 1;
    }

    return TreeLeafSize(root->pLeft) + TreeLeafSize(root->pRight);
}

int TreeHeight(BTNode* root){
    if (root == NULL){
        return 0;
    }

    int heiLeft = TreeHeight(root->pLeft);
    int heiRight = TreeHeight(root->pRight);

    return max(heiLeft + 1, heiRight + 1);

}

// 求二叉树第K层的节点个数
// 递归子问题(二叉数递归子问题，都转化为左子树和右子树)
// 返回条件(最小子问题)
// 当前树的第K层个数=左子树的第K-1层个数+右子树的第K-1层个数
int TreeKlevel(BTNode* root, int k)
{
    assert(k > 0);

    // 两个最小子问题顺序不可以调换
    if (root == NULL){
        return 0;
    }
    // 刚好到那一层，若调换，到那一层的NULL也会被统计
    if (k == 1){
        return 1;
    }

    int leftNums = TreeKlevel(root->pLeft, k - 1);
    int rightNums = TreeKlevel(root->pRight, k - 1);

    return leftNums + rightNums; // 也可以直接加起来，不存在二次调用的问题
}

// 找到第一个值为val的节点并返回
// 当前节点不是我们要找的节点
// 转成先在左子树找，没有找到，再去右子树找
// 前序相等，结构不一定相等
BTNode* TreeFind(BTNode* root, BTDataType val)
{
    if (root == NULL){
        return NULL;
    }
    if (root->data == val){
        return root;
    }

    // 先找左子树，没有再找右子树
    // 解决了找到答案调不出来的问题
    BTNode* retLeft = TreeFind(root->pLeft, val);
    if (retLeft){
        return retLeft;
    }

    BTNode* retRight = TreeFind(root->pRight, val);
    if (retRight){
        return retRight;
    }

    return NULL;
    // return TreeFind(root->pRight, val);
}

BTNode* CreateNewTree(BTDataType* data, int* pi)
{
    if (data[(*pi)] == '#'){
        (*pi)++;
        return NULL;
    }

    BTNode* root = (BTNode*)malloc(sizeof(BTNode));
    root->data = data[(*pi)++];
    root->pLeft = CreateNewTree(data, pi);
    root->pRight = CreateNewTree(data, pi);

    return root;
}

void TreeDestroy(BTNode* root)
{
    if (root == NULL){
        return ;
    }

    TreeDestroy(root->pLeft);
    TreeDestroy(root->pRight);
    free(root);
    root = NULL;
}

// 需要队列来层序遍历
void TreeLevelOrder(BTNode* root)
{
    Queue q;
    QueueInit(&q);
    if (root)
        QueuePush(&q, root);

    while (!isQueueEmpty(&q))
    {
        BTNode* front = QueueFront(&q);
        QueuePop(&q);

        if (front)
        {
            printf("%d ", front->data);
            // 带入下一层
            QueuePush(&q, front->pLeft);
            QueuePush(&q, front->pRight);
        }
        else
        {
            printf("N ");
        }
    }
    printf("\n");

    QueueDestroy(&q);
}

bool isCompleteTree(BTNode* root)
{
    Queue q;
    QueueInit(&q);
    if (root){
        QueuePush(&q, root);
    }
    while (!isQueueEmpty(&q)){
        BTNode* front = QueueFront(&q);
        QueuePop(&q);

        // 遇到空就跳出后续判断
        if (front == NULL){
            break;
        }

        QueuePush(&q, front->pLeft);
        QueuePush(&q, front->pRight);
    }

    // 如果都是空，就是完全二叉树
    while (!isQueueEmpty(&q)){
        BTNode* front = QueueFront(&q);
        QueuePop(&q);

        if (front){
            QueueDestroy(&q);
            return false;
        }
    }
    QueueDestroy(&q);
    return true;
}

int main(void)
{
    BTNode* root = CreateTree();

    printf("%d\n", TreeHeight(root));
    printf("%d\n", TreeKlevel(root, 2));

    printf("isCompleteTree:%d\n", isCompleteTree(root));

    TreeLevelOrder(root);

    TreeDestroy(root);
    root = NULL;
    return 0;
}

























